package LimitedTimeGame.Day_0223;

/**
 * @author zxc
 * @date 2023/02/23 11:31
 **/

import java.util.ArrayList;
import java.util.List;

/**
 * 题目 ：格雷编码
 * 题目详述 ：
 * n 位格雷码序列 是一个由 2^n 个整数组成的序列，其中：
 * 每个整数都在范围 [0, 2^n - 1] 内（含 0 和 2^n - 1）
 * 第一个整数是 0
 * 一个整数在序列中出现 不超过一次
 * 每对 相邻 整数的二进制表示 恰好一位不同 ，且
 * 第一个 和 最后一个 整数的二进制表示 恰好一位不同
 * 给你一个整数 n ，返回任一有效的 n 位格雷码序列
 *
 * 提示：
 * 1 <= n <= 16
 *
 */
public class GrayCode02 {
    /**
     * 思路 ：
     * （1）第一个整数必然为0;
     *  ===》 即，代表了 若是 n==0的话，则 0位格雷码序列为{0};
     * （2）1位格雷码序列中所包含的数字即为{0 , 1};
     * （3）n位格雷码序列 拥有2^n个整数，
     *  ===》
     *  a.前2^n-1个数字，即，对于n-1位格雷码序列来说，对其所有数字的最高位上加上0，然后顺序加入到 n位格雷码序列的前2^n-1个数字;
     *  （实质上，n位格雷码序列的前2^n-1个数字，就是n-1位格雷码序列中的数字;）
     *  b.后2^n-1个数字，即，对于n-1位格雷码序列中所有数字进行翻转，同时给每个数字的最高位上加上1，后加入到 n位格雷码序列的后2^n-1个数字;
     *  ===》
     *  从零位格雷码序列开始 依次类推，直至求至 n位格雷码序列;
     *
     * @param n
     * @return
     */
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        // 初始化 ：即，是 0位格雷码序列;
        // 由于 0是该格雷码序列的第一个整数;
        result.add(0);
        // 从 1位格雷码序列开始获取，直至 n位格雷码序列;
        for(int i = 0 ; i < n ; i++){
            int len = result.size();
            // 为求取 n位格雷码序列的 后2^n-1个数字，
            // 需要对于 n-1位格雷码序列结果进行反序获取，同时 与1 << n 进行异或操作;
            for(int j = len - 1 ; j >= 0 ; j--){
                result.add( result.get(j) | 1 << i);
            }
        }
        return result;
    }
}
